package com.cdream.basic.algorithm.leetcode.tree;

public class Offer7 {
    public TreeNode buildTree(int[] preorder, int[] inorder) {
        if (preorder.length == 0) {
            return null;
        }
        return buildTree(preorder, 0, preorder.length - 1, inorder, 0, inorder.length - 1);

    }

    private TreeNode buildTree(int[] preorder, int pStart, int pEnd, int[] inorder, int iStart, int iEnd) {
        if (iStart > iEnd || pStart > pEnd) {
            return null;
        }
        int root = preorder[pStart];
        int index = -1;
        for (int i = iStart; i <= iEnd; i++) {
            if (inorder[i] == root) {
                index = i;
                break;
            }
        }
        TreeNode r = new TreeNode(root);
        TreeNode left = buildTree(preorder, pStart + 1, pStart + index - iStart, inorder, iStart, index - 1);
        TreeNode right = buildTree(preorder, pStart + index - iStart+1, pEnd, inorder, index+1, iEnd);
        r.left = left;
        r.right = right;
        return r;
    }
}
